1. Technical Field
This invention concerns the routing of packets in packet-based networks.
2. Related Art
The performance of the internet is renowned for its inconsistency. Sometimes a document can be downloaded instantly; at other times, the same document takes a hundred times longer to appear. As a result, there is a lot of research effort directed at reducing internet congestion. Some groups favour resource rationing (K Danielsen and M Weiss, “User Control Modes and IP Allocation”, MIT Workshop on Internet Economics, March 1995), other groups seek to increase routing intelligence (G Di Caro and M Dorigo, “AntNet: Distributed Stigmergetic Control for Communication Networks”, J. Artificial Intelligence Research, 9, p. 317, 1998) to avoid congested regions of the network. It is generally understood that Shortest Path First (SPF) routing results in unnecessary congestion by focusing all traffic on to the same paths.
The problems associated with SPF are well understood. Some attempts to overcome this problems focus on traffic engineering, for example: Davie et al. (“Optimal use of multiple paths in IP networks, IEE 16th UK Teletraffic Symposium on ‘Management of quality of Service—The New Challenge’, Harlow, May 22-24, 2000), Holness and Phillips (“Dynamic QoS for MPLS Networks”, IEE 16th UK Teletraffic Symposium on ‘Management of quality of Service—The New Challenge’), Murphy et al (On Design of Diffserv/MPLS networks to Support VPNs, IEE 16th UK Teletraffic Symposium on ‘Management of quality of Service—The New Challenge’) and Webb (“Traffic Engineering in IP Networks: What Does it Offer?”, IEE 16th UK Teletraffic Symposium on ‘Management of quality of Service—The New Challenge’). Some of these approaches involve sophisticated schemes for speeding up traffic flow across a network. Currently, the idea of using explicit routes is popular. However, although the use of explicit routes is a workable traffic engineering mechanism, Davie et al. do not address how these routes should be chosen initially or under what conditions they should be activated. No criteria for path optimisation are proposed for use with this approach. Optimised paths could be set if traffic flow were predictable, but this is not the case. The Holness and Phillips scheme aims to guarantee QoS by reserving bandwidth for particular classes of traffic. Whilst guaranteed QoS is desirable, reserving resources is wasteful. Also, their dynamic choice of routes seems to require a heavy overhead of signalling and negotiation. The work by Murphy et al. considers traffic load balancing, but does not couple this to convergence on destination.